unit DIrr.Line2D;

{$I DIrr.inc}

interface

uses
  Math, DIrr.Math, DIrr.Vector2D;

type
  PLine2DF = ^TLine2DF;
  TLine2DF = record
    StartP: TVector2DF;
    EndP: TVector2DF;
  public
    class operator Add(Value: TLine2DF; Point: TVector2DF): TLine2DF;
    class operator Subtract(Value: TLine2DF; Point: TVector2DF): TLine2DF;
    class operator Equal(Value1, Value2: TLine2DF): Boolean;
    class operator NotEqual(Value1, Value2: TLine2DF): Boolean;

    procedure SetLine(const Sx, Sy, Ex, Ey: Single); overload;
    procedure SetLine(const StartV, EndV: TVector2DF); overload;
    procedure SetLine(const Line: TLine2DF); overload;

    function GetLength: Double;
    function GetSquaredLength: Double;
    function GetMiddle: TVector2DF;
    function GetVector: TVector2DF;

		//! Tests if this line intersects with another line.
		(* \param l: Other line to test intersection with.
		\param out: If there is an intersection, the location of the
		intersection will be stored in this vector.
		\return True if there is an intersection, false if not. *)
    function IntersectWith(const l: TLine2DF; var OutP: TVector2DF): Boolean;

		//! Get unit vector of the line.
		(* \return Unit vector of this line. *)
    function GetUnitVector: TVector2DF;

		//! Get angle between this line and given line.
		(* \param l Other line for test.
		\return Angle in degrees. *)
    function GetAngleWith(const l: TLine2DF): Double;

		//! Tells us if the given point lies to the left, right, or on the line.
		(* \return 0 if the point is on the line
		<0 if to the left, or >0 if to the right. *)
    function GetPointOrientation(const Point: TVector2DF): Single;

		//! Check if the given point is a member of the line
		(* \return True if point is between start and end, else false. *)
    function IsPointOnline(const Point: TVector2DF): Boolean;

		//! Check if the given point is between start and end of the line.
		(* Assumes that the point is already somewhere on the line. *)
    function IsPointBetweenStartAndEnd(const Point: TVector2DF): Boolean;

    //! Get the closest point on this line to a point
    function GetClosestPoint(const Point: TVector2DF): TVector2DF;

  end;

implementation



{ TLine2DF }

class operator TLine2DF.Add(Value: TLine2DF; Point: TVector2DF): TLine2DF;
begin
  Result.StartP := Value.StartP + Point;
  Result.EndP := Value.EndP + Point;
end;

class operator TLine2DF.Equal(Value1, Value2: TLine2DF): Boolean;
begin
  Result := ((Value1.StartP = Value2.StartP) and (Value1.EndP = Value2.EndP)) or
    ((Value1.StartP = Value2.EndP) and (Value1.EndP = Value2.StartP));
end;

function TLine2DF.GetAngleWith(const l: TLine2DF): Double;
var
  vect, vect2: TVector2DF;
begin
  vect := GetVector;
  vect2 := l.GetVector;

  Result := vect.GetAngleWith(vect2);
end;

function TLine2DF.GetClosestPoint(const Point: TVector2DF): TVector2DF;
var
  c, v: TVector2DF;
  d, t: Single;
begin
  c := Point - StartP;
  v := EndP - StartP;

  d := v.GetLength;
  v := v / d;
  t := v.DotProduct(c);

  if (t < 0.0) then
  begin
    Result := StartP;
    Exit;
  end;

  if (t > d) then
  begin
    Result := EndP;
    Exit;
  end;

  v := v * t;
  Result := StartP + v;
end;

function TLine2DF.GetLength: Double;
begin
  Result := StartP.DistanceFrom(EndP);
end;

function TLine2DF.GetMiddle: TVector2DF;
begin
  Result := (StartP + EndP) * 0.5;
end;

function TLine2DF.GetPointOrientation(const Point: TVector2DF): Single;
begin
  Result := (EndP.X - StartP.X) * (Point.Y - StartP.Y) -
    (Point.X - StartP.X) * (EndP.Y - StartP.Y);
end;

function TLine2DF.GetSquaredLength: Double;
begin
  Result := StartP.SquaredDistanceFrom(EndP);
end;

function TLine2DF.GetUnitVector: TVector2DF;
var
  len: Single;
begin
  len := 1.0 / GetLength;
  Result.X := (EndP.X - StartP.X) * len;
  Result.Y := (EndP.Y - StartP.Y) * len;
end;

function TLine2DF.GetVector: TVector2DF;
begin
  Result.X := EndP.X - StartP.X;
  Result.Y := EndP.Y - StartP.Y;
end;

function TLine2DF.IntersectWith(const l: TLine2DF;
  var OutP: TVector2DF): Boolean;
var
  CommonDenominator, NumeratorA, NumeratorB: Single;
  maxp, minp: TVector2DF;
  uA, uB: Single;
begin
  // Uses the method given at:
  // http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
  CommonDenominator := (l.EndP.Y - l.StartP.Y) * (EndP.X - StartP.X) -
    (l.EndP.X - l.StartP.X) * (EndP.Y - StartP.Y);

  NumeratorA := (l.EndP.X - l.StartP.X) * (StartP.Y - l.StartP.Y) -
    (l.EndP.Y - l.StartP.Y) * (StartP.X - l.StartP.X);

  NumeratorB := (EndP.X - StartP.X) * (StartP.Y - l.StartP.Y) -
    (EndP.Y - StartP.Y) * (StartP.X - l.StartP.X);

  if SameValue(CommonDenominator, 0.0, ROUNDING_ERROR_F32) then
  begin
    // The lines are either coincident or parallel
    // if both numerators are 0, the lines are coincident
    if SameValue(NumeratorA, 0.0, ROUNDING_ERROR_F32) and
      SameValue(NumeratorB, 0.0, ROUNDING_ERROR_F32) then
    begin
      // Try and find a common endpoint
      if (l.StartP = StartP) or (l.EndP = StartP) then
      begin
        OutP := StartP;
      end
      else if (l.EndP = EndP) or (l.StartP = EndP) then
      begin
        OutP := EndP;
      end
      // now check if the two segments are disjunct
      else if (l.StartP.X > StartP.X) and (l.EndP.X > StartP.X) and
        (l.StartP.X > EndP.X) and (l.EndP.X > EndP.X) then
      begin
        Result := False;
        Exit;
      end
      else if (l.StartP.Y > StartP.Y) and (l.EndP.Y > StartP.Y) and
        (l.StartP.Y > EndP.Y) and (l.EndP.Y > EndP.Y) then
      begin
        Result := False;
        Exit;
      end
      else if (l.StartP.X < StartP.X) and (l.EndP.X < StartP.X) and
       (l.StartP.X < EndP.X) and (l.EndP.X < EndP.X) then
      begin
        Result := False;
        Exit;
      end
      else if (l.StartP.Y < StartP.Y) and (l.EndP.Y < StartP.Y) and
        (l.StartP.Y < EndP.Y) and (l.EndP.Y < EndP.Y) then
      begin
        Result := False;
        Exit;
      end
      // else the lines are overlapping to some extent
      else
      begin
        // find the points which are not contributing to the
        // common part
        if ((StartP.X > l.StartP.X) and (StartP.X > l.EndP.X) and (StartP.X > EndP.X)) or
          ((StartP.Y > l.StartP.Y) and (StartP.Y > l.EndP.Y) and (StartP.Y > EndP.Y)) then
        begin
          maxp := StartP;
        end
        else if ((EndP.X > l.StartP.X) and (EndP.X > l.EndP.X) and (EndP.X > StartP.X)) or
          ((EndP.Y > l.StartP.Y) and (EndP.Y > l.EndP.Y) and (EndP.Y > StartP.Y)) then
        begin
          maxp := EndP;
        end
        else if ((l.StartP.X > StartP.X) and (l.StartP.X > l.EndP.X) and (l.StartP.X > EndP.X)) or
          ((l.StartP.Y > StartP.Y) and (l.StartP.Y > l.EndP.Y) and (l.StartP.Y > EndP.Y)) then
        begin
          maxp := l.StartP;
        end
        else
        begin
          maxp := l.EndP;
        end;

        if (maxp <> StartP) and
          (((StartP.X < l.StartP.X) and (StartP.X < l.EndP.X) and (StartP.X < EndP.X)) or
           ((StartP.Y < l.StartP.Y) and (StartP.Y < l.EndP.Y) and (StartP.Y < EndP.Y))) then
        begin
          minp := StartP;
        end
        else if (maxp <> EndP) and
          (((EndP.X < l.StartP.X) and (EndP.X < l.EndP.X) and (EndP.X < StartP.X)) or
           ((EndP.Y < l.StartP.Y) and (EndP.Y < l.EndP.Y) and (EndP.Y < StartP.Y))) then
        begin
          minp := EndP;
        end
        else if (maxp <> l.StartP) and
          (((l.StartP.X < StartP.X) and (l.StartP.X < l.EndP.X) and (l.StartP.X < EndP.X)) or
           ((l.StartP.Y < StartP.Y) and (l.StartP.Y < l.EndP.Y) and (l.StartP.Y < EndP.Y))) then
        begin
          minp := l.StartP;
        end
        else
        begin
          minp := l.EndP;
        end;

        // one line is contained in the other. Pick the center
        // of the remaining points, which overlap for sure
        OutP.X := 0.0;
        OutP.Y := 0.0;
        if (StartP <> maxp) and (StartP <> minp) then
          OutP := OutP + StartP;
        if (EndP <> maxp) and (EndP <> minP) then
          OutP := OutP + EndP;
        if (L.StartP <> maxp) and (l.StartP <> minp) then
          OutP := OutP + l.StartP;
        if (l.EndP <> maxp) and (l.EndP <> minp) then
          OutP := OutP + l.EndP;
        OutP := OutP * 0.5;
      end;

      Result := True;
      Exit;
    end;

    Result := False;
    Exit;
  end;

  // Get the point of intersection on this line, checking that
  // it is within the line segment.
  uA := NumeratorA / CommonDenominator;
  if (uA < 0.0) or (uA > 1.0) then
  begin
    Result := False;        // Outside the line segment
    Exit;
  end;

  uB := NumeratorB / CommonDenominator;
  if (uB < 0.0) or (uB > 1.0) then
  begin
    Result := False;        // Outside the line segment
    Exit;
  end;

  // Calculate the intersection point.
  OutP.X := StartP.X + uA * (EndP.X - StartP.X);
  OutP.Y := StartP.Y + uA * (EndP.Y - StartP.Y);
  Result := True;
end;

function TLine2DF.IsPointBetweenStartAndEnd(
  const Point: TVector2DF): Boolean;
begin
  Result := Point.IsBetweenPoints(StartP, EndP);
end;

function TLine2DF.IsPointOnline(const Point: TVector2DF): Boolean;
var
  d: Single;
begin
  d := GetPointOrientation(Point);
  Result := SameValue(d, ROUNDING_ERROR_F32) and Point.IsBetweenPoints(StartP, EndP);
end;

class operator TLine2DF.NotEqual(Value1, Value2: TLine2DF): Boolean;
begin
  Result := not (((Value1.StartP = Value2.StartP) and (Value1.EndP = Value2.EndP)) or
    ((Value1.StartP = Value2.EndP) and (Value1.EndP = Value2.StartP)));
end;

procedure TLine2DF.SetLine(const Sx, Sy, Ex, Ey: Single);
begin
  StartP.X := Sx;
  StartP.Y := Sy;
  EndP.X := Ex;
  EndP.Y := Ey;
end;

procedure TLine2DF.SetLine(const StartV, EndV: TVector2DF);
begin
  StartP := StartV;
  EndP := EndV;
end;

procedure TLine2DF.SetLine(const Line: TLine2DF);
begin
  Self := Line;
end;

class operator TLine2DF.Subtract(Value: TLine2DF; Point: TVector2DF): TLine2DF;
begin
  Result.StartP := Value.StartP - Point;
  Result.EndP := Value.EndP - Point;
end;

end.